科目名 □データ構造とアルゴリズムⅢ
担当教員   古井 陽之助     
対象学年   3年   クラス   [404]  
講義室   12109教室   開講学期   前期  
曜日・時限   金4   単位区分   選択  
授業形態     単位数   2  
準備事項    
備考    

講義概要/Class Outline

コンピュータを用いると、大量のデータを効率よく処理できるのみならず、精度の高い数値計算や、複雑な構造を持つデータの処理が可能になる。「データ構造とアルゴリズムI」「同II」までは大量のデータを効率よく処理するためのデータ構造やアルゴリズムを扱った。本講義ではこれらの講義に続き、誤差を考慮した数値計算のアルゴリズム、ハッシュ表、ヒープ、ヒープソート、グラフの表現と応用を取り上げる。  

講義計画 /Class Structure

内容
1 数値計算と誤差(1) 計算機内部の数値表現
2 数値計算と誤差(2) 計算機を用いた数値計算での様々な誤差
3 数値計算と誤差(3) 誤差を考慮した数値計算
4 応用データ構造(1) 集合の表現と操作
5 応用データ構造(2) ハッシュ関数
6 応用データ構造(3) ハッシュ表
7 応用データ構造(4) ヒープ
8 応用アルゴリズム ヒープソート
9 グラフの表現 隣接行列と隣接リスト
10 グラフの応用(1) 深さ優先探索と幅優先探索
11 グラフの応用(2) 最短路アルゴリズム
12 グラフの応用(3) 最小スパニング木
13 まとめ(1)
14 まとめ(2)
 

学習・教育目標/Class Target 1. 数値計算と誤差の基礎的な事項について理解し、誤差を考慮した数値計算のプログラムを作成できる。
2. ハッシュの基本概念とハッシュ表の操作を理解し、ハッシュ表の応用ができる。
3. ヒープとヒープソート、グラフの表現を理解し、グラフの応用ができる。  
評価基準/GradingCriteria 秀:評価方法の総点が満点の9割以上
優:評価方法の総点が満点の8割以上
良:評価方法の総点が満点の7割以上
可:評価方法の総点が満点の6割以上  
評価方法/GradingMethod 定期試験、小テスト、演習の合計点(比率は3:1:1)を総点とする。  
受講上の注意/Class Rules 関連科目を復習しておくこと。貸与ノートパソコンを忘れずに持ってくること。  
受講制限/Prerequisit  
関連する科目/Related Class プログラミング基礎、データ構造とアルゴリズムI、データ構造とアルゴリズムII、離散数学III-A、離散数学III-B  
教科書/Text
著者名 権藤 克彦  
著書名 Javaによるプログラミング入門(1年次に購入済みの教科書を使用)  
出版社名 サイエンス社  
ISBNコード 978-4-7819-0942-4  
指定図書/Assigned Books
著者名 五十嵐 健夫  
著書名 データ構造とアルゴリズム  
出版社名 数理工学社  
ISBNコード 978-4-9016-8349-4  
著者名 近藤 嘉雪  
著書名 Javaプログラマのためのアルゴリズムとデータ構造  
出版社名 ソフトバンク  
ISBNコード 978-4-7973-2660-4  
著者名 Robert Lafore, 岩谷 宏(翻訳)  
著書名 Javaで学ぶアルゴリズムとデータ構造  
出版社名 ソフトバンク  
ISBNコード 978-4-7973-0694-1  
参考文献/Bibliography
著者名 伊藤 正夫, 藤野 和建  
著書名 数値計算の常識  
>出版社名 共立出版  
ISBNコード 978-4-3200-1343-8  
著者名 奥村 晴彦, 杉浦 方紀, 津留 和生, 首藤 一幸, 土村 展之  
著書名 Javaによるアルゴリズム事典  
>出版社名 技術評論社  
ISBNコード 978-4-7741-1729-4  
著者名 T. H. Cormen, C. Stein, R. L. Rivest, C. E. Leiserson, 浅野 哲夫(翻訳), 岩野 和生 (翻訳)ほか  
著書名 アルゴリズムイントロダクション改訂2版 第1巻 数学的基礎とデータ構造  
>出版社名 近代科学社  
ISBNコード 978-4-7649-0334-0  
著者名 T. H. Cormen, C. Stein, R. L. Rivest, C. E. Leiserson, 浅野 哲夫(翻訳), 岩野 和生 (翻訳)ほか  
著書名 アルゴリズムイントロダクション改訂2版 第2巻 アルゴリズムの設計と解析手法  
>出版社名 近代科学社  
ISBNコード 978-4-7649-0335-7